NOIP2015 普及组

Actinoi 8月 26, 2019

T1:金币

题目描述

国王将金币作为工资，发放给忠诚的骑士。第一天，骑士收到一枚金币；之后两天（第二天和第三天），每天收到两枚金币；之后三天（第四、五、六天），每天收到三枚金币；之后四天（第七、八、九、十天），每天收到四枚金币……；这种工资发放模式会一直这样延续下去：当连续N天每天收到N枚金币后，骑士会在之后的连续天里，每天收到枚金币。

请计算在前天里，骑士一共获得了多少金币。

输入格式

一个正整数，表示发放金币的天数。

输出格式

一个正整数，即骑士收到的金币数。

输入输出样例

输入样例 #1

输出样例 #1

输入样例 #2

输出样例 #2

说明/提示

【输入输出样例 1 说明】

骑士第一天收到一枚金币；第二天和第三天，每天收到两枚金币；第四、五、六天，每天收到三枚金币。因此一共收到枚金币。

对于的数据，。

NOIP2015 普及组第一题

题解：

本题为一个模拟题。设置一个变量用来记录要发的金币数量与要发的天数。然后将从枚举到，将从枚举到，最后输出总钱数就可以。

#include <iostream>
using namespace std;
int main() {
    int k;
    cin >> k;
    int p = 1, ans = 0;
    for (int i = 1; i <= k; i++) {
        i--;
        for (int j = 1; j <= p; j++) {
            i++;
            ans += p;
            if (i == k) {
                cout << ans << endl;
                return 0;
            }
        }
        p++;
    }
    return 0;
}

T2: 扫雷游戏

题目描述

扫雷游戏是一款十分经典的单机小游戏。在行列的雷区中有一些格子含有地雷（称之为地雷格），其他格子不含地雷（称之为非地雷格）。玩家翻开一个非地雷格时，该格将会出现一个数字——提示周围格子中有多少个是地雷格。游戏的目标是在不翻出任何地雷格的条件下，找出所有的非地雷格。

现在给出行列的雷区中的地雷分布，要求计算出每个非地雷格周围的地雷格数。

注：一个格子的周围格子包括其上、下、左、右、左上、右上、左下、右下八个方向上与之直接相邻的格子。

输入格式

第一行是用一个空格隔开的两个整数和，分别表示雷区的行数和列数。

接下来行，每行个字符，描述了雷区中的地雷分布情况。字符’*’表示相应格子是地雷格，字符’?’表示相应格子是非地雷格。相邻字符之间无分隔符。

输出格式

输出文件包含行，每行个字符，描述整个雷区。用’*’表示地雷格，用周围的地雷个数表示非地雷格。相邻字符之间无分隔符。

输入输出样例

输入样例 #1

3 3
*??
???
?*?

输出样例 #1

*10
221
1*1

输入样例 #2

2 3
?*?
*??

输出样例 #2

2*1
*21

说明/提示

对于的数据，。

NOIP2015 普及组第二题

题解：

本题直接模拟就可以。

我们枚举每个点，如果这个点为 '*' 的话，那么便输出 '*' ，否则找这个点上、下、左、右、左上、右上、左下、右下八个方向雷的总数，并且输出这个数量就可以。

#include <iostream>
using namespace std;
char minefield[102][102]; //存储雷区
int find (int i, int j) { //寻找雷
    int ans = 0;
    for (int i1 = i - 1; i1 <= i + 1; i1++)
        for (int j1 = j - 1; j1 <= j + 1; j1++)
            if (minefield[i1][j1] == '*')
                ans++;
    return ans;
}
int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> minefield[i][j];
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (minefield[i][j] == '*')
                cout << "*";
            else
                cout << find(i, j);
        }
        cout << endl;
    }
    return 0;
}

T3:求和

题目描述

一条狭长的纸带被均匀划分出了个格子，格子编号从到。每个格子上都染了一种颜色用当中的一个整数表示），并且写了一个数字。

定义一种特殊的三元组：，其中都代表纸带上格子的编号，这里的三元组要求满足以下两个条件：

是整数,
满足上述条件的三元组的分数规定为。

整个纸带的分数规定为所有满足条件的三元组的分数的和。这个分数可能会很大，你只要输出整个纸带的分数除以所得的余数即可。

输入格式

第一行是用一个空格隔开的两个正整数和表纸带上格子的个数，表纸带上颜色的种类数。

第二行有用空格隔开的正整数，第数字表纸带上编号为格子上面写的数字。

第三行有用空格隔开的正整数，第数字表纸带上编号为格子染的颜色。

输出格式

一个整数，表示所求的纸带分数除以所得的余数。

输入输出样例

输入样例 #1

6 2
5 5 3 2 2 2
2 2 1 1 2 1

输出样例 #1

输入样例 #2

15 4
5 10 8 2 2 2 9 9 7 7 5 6 4 2 4
2 2 3 3 4 3 3 2 4 4 4 4 1 1 1

输出样例 #2

说明/提示

【输入输出样例 1 说明】

纸带如题目描述中的图所示。

所有满足条件的三元组为：。

所以纸带的分数为。

对于第组至第组数据，；

对于第组至第组数据，，且不存在出现次数超过的颜色；

对于全部组数据，

NOIP2015 普及组第三题

题解：

直接枚举本题的话是过不了的。因此，我们便考虑用一些玄学的方法来做这道题。

我们只需要枚举与就可以。为什么呢？因为若存在特殊的三元组：的话，那么，。

我们在进一步讨论与的问题。首先，与必须要颜色相同，因此，我们可以将相同颜色的放个存储在一个相同数组中。其次，与的编号可能是一奇一偶吗？我们分析一下，如题目图片，

若编号编号的话，那么，因此便不存在了。所以，我们可以相同颜色的再分一下奇偶性，这样又做到了一步优化。

然后，若一个相同颜色相同奇偶性的数组中有个元素。因此，这个数组中特殊三元组的个数也就是：

拆开上面的式子，也就是：

合并上面的式子：

进一步化简，得到：

因此，我们只需要统计一下的前缀和就可以了，然后带入推出来的式子就 OK 啦！

#include <iostream>
#define MOD 10007
using namespace std;
int number[100001], cnt[100001][2], sum[100001][2], p[100001];
int main() {
    int n, m; //n表纸带上格子的个数，m表纸带上颜色的种类数
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> number[i];
    for (int i = 1; i <= n; i++) {
        cin >> p[i]; //读入标号为 i 的格子的颜色
        cnt[p[i]][i % 2]++;
        sum[p[i]][i % 2] = (sum[p[i]][i % 2] + number[i]) % MOD; //计算前缀和
    }
    int ans = 0;
    for (int i = 1; i <= n; i++)
        ans = ans + i * (number[i] % MOD * (cnt[p[i]][i % 2] - 2) % MOD + sum[p[i]][i % 2]) % MOD;
    cout << ans % MOD << endl;
    return 0;
}

T4:推销员

题目描述

阿明是一名推销员，他奉命到螺丝街推销他们公司的产品。螺丝街是一条死胡同，出口与入口是同一个，街道的一侧是围墙，另一侧是住户。螺丝街一共有家住户，第家住户到入口的距离为米。由于同一栋房子里可以有多家住户，所以可能有多家住户与入口的距离相等。阿明会从入口进入，依次向螺丝街的家住户推销产品，然后再原路走出去。

阿明每走米就会积累点疲劳值，向第家住户推销产品会积累点疲劳值。阿明是工作狂，他想知道，对于不同的，在不走多余的路的前提下，他最多可以积累多少点疲劳值。

输入格式

第一行有一个正整数，表示螺丝街住户的数量。

接下来的一行有个正整数，其中第个整数表示第家住户到入口的距离。数据保证。

接下来的一行有个正整数，其中第个整数表示向第户住户推销产品会积累的疲劳值。数据保证。

输出格式

输出行，每行一个正整数，第i行整数表示当时，阿明最多积累的疲劳值。

输入输出样例

输入样例 #1

5
1 2 3 4 5
1 2 3 4 5

输出样例 #1

输入样例 #2

5
1 2 2 4 5
5 4 3 4 1

输出样例 #2

说明/提示

【输入输出样例1说明】

:向住户推销，往返走路的疲劳值为，推销的疲劳值为，总疲劳值为。

:向住户推销，往返走路的疲劳值为，推销的疲劳值，总疲劳值为。

:向住户推销，往返走路的疲劳值为，推销的疲劳值，总疲劳值。

【输入输出样例2说明】

：向住户推销，往返走路的疲劳值为，推销的疲劳值为，总疲劳值。

：向住户推销，往返走路的疲劳值为，推销的疲劳值为，总疲劳值。或者向住户推销，往返走路的疲劳值为，推销的疲劳值为，总疲劳值。

：向住户推销，往返走路的疲劳值为，推销的疲劳值为，总疲劳值。

【数据说明】

对于的数据，；

对于的数据，。

NOIP2015 普及组第四题

题解：

本题可以用贪心的策略来完成。

按照疲劳值进行结构体排序，然后设置数组存储之后的距离与疲劳值最大和。

接着，用枚举之前的前缀和。对于每个，选择一个最大的距离 (个最大的路程 ) 或者个最大的路程永远是最优的。因此，输出 max(前 i - 1 的前缀和 + i 后面最大的路程, 前 i 的前缀和 + 2 * 路程) 就可以。

#include <iostream>
#include <algorithm>
using namespace std;
struct node {
    int s, a;
} salesman[100001];
int t[100002], sum[100001], q[100001]; //sum 存储前缀和
bool cmp (node x, node y) {
    return x.a > y.a;
}
int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> salesman[i].s;
    for (int i = 1; i <= n; i++)
        cin >> salesman[i].a;
    sort(salesman + 1, salesman + 1 + n, cmp); //按照疲劳值进行排序
    for (int i = n; i >= 1; i--)
        t[i] = max(t[i + 1], salesman[i].s * 2 + salesman[i].a);
    for (int i = 1; i <= n; i++) {
        sum[i] = sum[i - 1] + salesman[i].a; //前缀和
        q[i] = max(q[i - 1], salesman[i].s); //最大距离
        cout << max(sum[i - 1] + t[i], sum[i] + 2 * q[i]) << endl;
    }
    return 0;
}

T1:金币

题目描述

输入格式

输出格式

输入输出样例

输入样例 #1

输出样例 #1

输入样例 #2

输出样例 #2

说明/提示

题解：

T2: 扫雷游戏

题目描述

输入格式

输出格式

输入输出样例

输入样例 #1

输出样例 #1

输入样例 #2

输出样例 #2

说明/提示

题解：

T3:求和

题目描述

输入格式

输出格式

输入输出样例

输入样例 #1

输出样例 #1

输入样例 #2

输出样例 #2

说明/提示

题解：

T4:推销员

题目描述

输入格式

输出格式

输入输出样例

输入样例 #1

输出样例 #1

输入样例 #2

输出样例 #2

说明/提示

题解：

T2: 扫雷游戏